Mythili's Gift Card Challenge
Given a list of item prices and a gift card balance (target), the task is to determine if a **subset** of items exists whose total price exactly equals the gift card balance. If multiple exist, we must find and output the **first one found** by the search process.
Required Calculation and Output
- **Line 1:** Print the result of the formula: $Target \times 2 - 1$.
- **Line 2:** Print the space-separated item prices of the **first occurring combination** that matches the target, or "No combination of items."
Sample Input/Output
Input (Sample 1 - Success):
3
10 20 30
50
Output:
99
20 30
Input (Sample 2 - Failure):
4
10 15 20 30
58
Output:
115
No combination of items
Backtracking Algorithm (First Match)
This solution uses the **Backtracking** technique to explore the decision space (Include/Exclude each item). Unlike counting, we optimize the search by stopping immediately upon finding the first valid subset.
Core Logic
- **Stopping Condition:** Once the `currentSum` equals the `target`, the solution is stored, and the recursion unwinds immediately by passing a `true` signal up the call stack, preventing further branches from executing.
- **Two Choices:** At each item index, the recursive function attempts to **Include** the item. If the 'Include' branch doesn't find the solution, it then tries to **Exclude** the item.
Base Cases
- **Success:** If `currentSum === target`, store the subset and return `true` (found).
- **Failure/Pruning:** If `currentSum > target` or if all items are processed, return `false` (not found on this path).
Dynamic Execution Trace
Enter input and click "Execute Calculation" to see the full backtracking trace flow here.